package com.leetcode;

import java.util.Stack;

/*Valid Parentheses(圆括号)
 Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
 The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.*/

public class Solution
{
	public boolean isValid(String s)
	{
		Stack<Character> left = new Stack<Character>();
		for (int i = 0; i < s.length(); i++)
		{
			char c = s.charAt(i);
			if (c == ')')
			{
				if (left.empty() || left.pop() != '(')
				{
					return false;
				}
			}
			else if (c == ']')
			{
				if (left.empty() || left.pop() != '[')
				{
					return false;
				}
			}
			else if (c == '}')
			{
				if (left.empty() || left.pop() != '{')
				{
					return false;
				}
			}
			else
			{
				left.push(c);
			}
		}
		return left.empty();
	}
}